The present invention is related to a method and apparatus for accessing a multi-bank memory and in particular to a method and apparatus which can increase effective bandwidth of such access.
A number of techniques have been used or proposed in connection with multi-bank memory systems for providing high bandwidth access. In one technique, if there are, e.g., two banks, it can be advantageous to configure the system such that while a row or page of data is being read-out from one of the banks, a page-opening procedure (for the data which is to be readout from the next bank) is being performed on the second bank. Ideally, by the time data readout from the first bank is complete, the second bank has completed its page-opening procedures and data-readout from the second bank can begin immediately (i.e., in the next clock cycle, following the clock cycle in which the last data was read-out from the first bank). Such techniques can be especially useful when multiple rows or pages of data are commonly read-out from alternative banks. One example of the situation is when a multi-bank memory is used for first-in-first-out (FIFO) storage or buffering of data packets or frames in a network or telecommunication system. It is common, in these situations, for the frame length to exceed a single page width and accordingly, it is common for data to be stored into, and read-out from, pages of alternating banks of the memory.
In an ideal situation, if the xe2x80x9ceffective bandwidthxe2x80x9d is expressed as the number of words read-out from the memory (over an extended period of time) divided by the number of clock cycles occupied by such read-out, in an ideal situation, the bandwidth would be 1.0. In other words, in an ideal situation, one word is read-out for every clock cycle, over an extended period of time. In practice, it has been found that the effective bandwidth for multi-bank memories is typically somewhat less than ideal. Accordingly, it would be useful to provide a system method and apparatus which can increase the effective bandwidth of a multi-bank memory system.
The present invention includes a recognition of the existence, nature, significance and/or consequences of problems in previous approaches, including as described herein. When frames or other blocks of data are stored into pages of memory, situations may arise in which the number of words in the frame is not an integral multiple of the number of words in a page. Accordingly, the last page in the memory used for storing the last portion of the frame may be less than full. As one (simplified) example, if a fame contains 25 words and a page has a width of 8 words, the frame can be stored in 4 pages (3 pages of 8 words each and a final page containing a single word). As described above, in at least some systems, while data is being read-out from a page in a first bank of memory, page-opening procedures are being performed in the second bank, for the next page which is to be read-out. In the present example, if page-opening procedures require two (or more) clock cycles, there will be insufficient time to complete page-opening procedures (for the next bank) during the time that the single word stored in the last page (for the 25-word frame) is performed. If only one clock cycle is needed for reading out the single word from the last page of the 25-word frame, two-clock-cycle page-opening procedures for opening the first page of whatever data is to be read-out next (i.e., after the 25 word frame has been read-out) will not be complete and there will be at least one clock cycle (referred to as xe2x80x9cdead timexe2x80x9d) during which no data is read-out (i.e., the second clock cycle required to complete page-opening procedures for the next read-out). Any occurrence of such xe2x80x9cdead timexe2x80x9d cycles will reduce the long-term effective bandwidth to a less-than-ideal value.
According to one embodiment of the invention, data is stored into pages of memory in a multi-bank memory in such a way as to avoid such dead time during subsequent read-out. According to one embodiment, when it is determined that storage of a block of data in the traditional manner will result in a page which stores a number of words, in one of the pages, which is smaller than the number of clock cycles required to open a page, the words of the frame or block will instead be stored in a non-traditional manner so as to increase the number of words in the last page or pages, preferably such that all pages used for storing the frame have a number of words equal to or greater than the number of clock cycles required for page-opening processes. As one example, if 8-word pages are to be used for storing a 25-word frame, and if page-opening requires two clock cycles, then the 25 words can be stored in a total of 4 pages: 2 pages storing 8 words each, 1 page storing 7 words and a final page storing 2 words. Since the final page, in this example, stores 2 words, it is possible to complete page-opening processes for whichever page is to be read-out after the 25 page frame, during the time that the 2 words in the final page are read-out.
For purposes of explanation, the process of reducing the number of words stored in one page so that the number of words stored in a different page can be increased, is referred to herein as xe2x80x9cborrowingxe2x80x9d one or more words from the page in which the number of words is decreased.
At least some aspects of the present invention can be advantageously used regardless of the number of words in a page or the number of clock cycles needed for page-opening (if, in a two-bank example, the number of the required clock cycles does not exceed the number of words in a page). In general, the present invention is capable of eliminating all dead time caused by pages with fewer words than the number of cycles needed for page-opening if the number of xe2x80x9cextraxe2x80x9d words in a frame in excess of a multiple of the word width (i.e., the frame length modulo the page width) plus the page width is greater than or equal to twice the number of clock cycles required for page-opening.
In one aspect, data is stored in a memory in a manner which eliminates dead time which occurs when the number of words in a page which are read-out are insufficient to provide enough time for simultaneously opening the next page. If the length of a frame being stored in memory is not an exact integral multiple of words in a page, a penultimate (or earlier) page is written with fewer words than the page can hold. This allows additional words to be placed into the last page, sufficient to provide every page used for storing a frame at least a number of words equal to the number of clock cycles needed for opening a next page.